package com.example.leetdemo.finash;

public class Solution779 {

    public int kthGrammar(int n, int k) {
        return findRoot(n, k);
    }

    public int findRoot(int n, int k) {
        if (n == 1) {
            return 0;
        }
        int num = 0;
        int lastLength = (k + 1) / 2;
            num = findRoot(n - 1, lastLength);
        return k % 2 == 1 ? num : num ^ 1;
    }

    public static void main(String[] args) {
        Solution779 solution779 = new Solution779();
        System.err.println(solution779.kthGrammar(3, 1));
    }

}
